One of the most important, value-adding features in a computer is its ability to process large amounts of data and information. Some of the information frequently processed by a computer includes image and other signal information. Frequently, information processed on a computer may relate to the general computer display, computer graphics, scanned images, video, and other data. With each of these types of data, it is often desirable to utilize the convolution function to process the data.
Convolution is useful in demonstrating the manner in which two signals interact in the time domain, and in expressing a resulting signal from the mixing of the two signals within the time domain. Mathematically, convolution is the multiplication of two sequences, which can be expressed in the form of an integral shown below in equation 1.
                              y          ⁡                      (            t            )                          =                                            f              ⁡                              (                t                )                                      ⁢                        ⁢                          g              ⁡                              (                t                )                                              ≡                                    ∫                              -                ∞                            ∞                        ⁢                                          f                ⁡                                  (                  τ                  )                                            ⁢                                                          ⁢                              g                ⁡                                  (                                      t                    -                    τ                                    )                                            ⁢                              ⅆ                                                                  ⁢                τ                                                                        (        1        )            
In Equation 1, two signals f(t) and g (t) are convolved to yield the resulting signal y(t). The far right side of Equation 1 shows the general convolution integral wherein the signals are expressed in terms of τ and t−τ, as a sliding function. This convolution integral exhibits various useful properties. For example, the convolution operation is commutative, distributive, and associative and allows shifting of the resulting y (t) by the same amount as the input signals f(t) and g(t). The width along the t-axis of the resulting signal y(t) is the combined width of the two input signals f(t) and g(t).
Convolution may also be performed using a digital or discrete method. In this manner, the convolution integral is expressed as a convolution sum. Equation 2 below shows a general convolution sum.
                              y          ⁡                      [            k            ]                          =                                            f              ⁡                              [                k                ]                                      ⁢                        ⁢                          g              ⁡                              [                k                ]                                              =                                                                      lim                                                                                                  T                    →                    0                                                                        ⁢                                          ∑                                  m                  =                                      -                    ∞                                                  ∞                            ⁢                                                          ⁢                                                f                  ⁡                                      [                    m                    ]                                                  ⁢                                  g                  ⁡                                      [                                          k                      -                      m                                        ]                                                                                                          (        2        )            This convolution sum is the discrete-time equivalent of the convolution integral shown in Equation 1. In Equation 2, two discrete input signals f[k] and g[k] are convolved using the convolution sum to obtain the resulting signal y[k]. One of the signals is reflected about the y-axis and translated over the entire range of values of m (in this case the width of g[k]), whereupon the values of the two signals are multiplied together at each commonly shared discrete location and the products of each value of m are summed. T represents the sampling frequency, or sampling interval. This is the interval at which samples of the continuous functions are taken and corresponds to the spacing between discrete values of the discrete functions. Using the discrete convolution sum allows a computer to perform discrete convolution calculation.
One of the main problems in performing convolution using a computer is that the process is inherently linear. For relatively long sequences, therefore, the convolution process can be quite lengthy. Generally, a computer reads each function to be convolved as a stream of data, one element at a time. This requires valuable processor time, and the time required increases proportionately to the complexity and length of the signals to be processed. This is especially problematic, for example, in image processing applications and/or video applications, where signals are complex and memory-intensive. In video applications, another problem arises in that the real-time display of images, which is essential for a user's understanding in viewing the video information, requires numerous computations at a high rate of speed without delays. If the convolution sum used to process these video signals delays the output of the video, the result may be difficulty in understanding the output signal.
As processor speeds and users' demands for quality increase, it is essential that signals which are processed by way of a convolution sum, such as the one shown in Equation 2, are processed in the most efficient manner without sacrificing quality. Even with the increased processor speeds of today, performing convolution as a serial process whereby entire streams of data are input, output, and computed sequentially, slows a computer's ability to process signals and information, and generally slows the processing of data involved in unrelated functions by the computer.
Recently, vector processing, which utilizes parallel computing operations, has been implemented in various computer systems. This type of computer processing has the advantage that multiple calculations may be performed simultaneously. This is accomplished by using vector calculations whereby entire matrices may be added, subtracted, multiplied, divided, or otherwise operated upon. However, even with the increased speeds afforded by performing vector calculations in a vector processing computer system, convolution has traditionally been a serial operation that does not take advantage of the vector processing power. As a result, an efficient, vector processing system may perform multiple tasks using parallel computing and not make use of the parallel calculating capability for convolution operations, thereby slowing the entire system while awaiting the results of a convolution calculation. The diminished processing speed is further exacerbated by the fact that linear processing typically occurs in a part of the computer's central processing unit separate from the vector processor. Consequently, the delays associated with transferring data between the linear and vector processors further slow the overall process.
Accordingly, it is desirable to create a system and method for performing convolution in a vector processing computer system that utilizes the parallel calculating capability of the system in a manner so as to make the most efficient use of the computer system.